package com.ftg.learn.chapter05;

import java.util.Arrays;

/**
 * 我们想自己设计一个，长度可以变化的数组，或者自定义引用类型
 * 以后用我们这个类型，可以向里面存储大量相同类型数据
 *
 * @author kangjx
 * @date 2022/12/17
 */
public class ChangeArray {

    /**
     * 我们先设计一个数组的下标
     * ,用来纪录你存储了几个数据
     * index++
     */
    int index = 0;

    /**
     * 还要有一个用来存储我们数组地址 对应的标识符，
     * 标识符不变，地址变化,默认情况下，我们的数组初始长度为10
     * 出阶段最多可以存储 10个int
     */
    int[] arr = new int[10];

    /**
     * 成员方法,
     * 写一个向arr里面添加int的方法
     *
     * @param x 值
     */
    public boolean add(int x) {
        //如果数组长度与下标相等 说明? 数组里面存满了 变地址

        //扩容  扩大容量 .....
        if (arr.length == index) {
//            //中庸之道 arr.length + 1 》》 >>
//            int[] temp = arr;
//            //原长度的1.5倍
//            //容错吗?
////            int oldLen = arr.length;
////            //计算出来新长度
////            long newLen = arr.length >> 1 + oldLen;
////            if(newLen > Integer.MAX_VALUE){
////                arr = new int[Integer.MAX_VALUE];
////            }else{
////                arr = new int[arr.length >> 1 + oldLen];
////            }
//            arr = new int[(arr.length >> 1) + arr.length];
//            for (int i = 0; i < temp.length; i++) {
//                arr[i] = temp[i];
//            }
            arr = Arrays.copyOf(arr,(arr.length >> 1) + arr.length);
        }
        arr[index++] = x;
        return true;
    }

    /**
     * 这个数据里面有没有某一个数呀
     *
     * @param target 目标数
     * @return boolean
     */
    public boolean exists(int target) {
        //你们认为这样写有没有问题?
//        int j = size();//调用方法
//        int j = index;//调用属性
        /**
         * i 代表从0开始看有没有
         * j 代表从最后一个有效位置看有没有
         */
        for (int i = 0, j = size() - 1; i <= j; i++, j--) {
            if (arr[i] == target || arr[j] == target) {
                return true;
            }
        }
        return false;
    }

    /**
     * 是否可以有一个根据下标求下标真实数据的方法
     *
     * @param subscript 索引 从 1 开始
     * @return int
     */
    public int findVal(int subscript) {
        if (subscript < 1 || subscript > index) {
            System.out.println("您传递给我的数组下标范围出错，应该为大于等于1,小于" + index);
        }
        return arr[subscript - 1];
    }

    /**
     * 调整处理 :
     * 无序数组
     * [1,2,4,6,8,2,9,10]  10W  5W
     *
     * 有序数组
     * [1,2,2,4,6,8,9,10] 二分查找 拆半查找
     * --> 0 - inf
     */
    /**
     * 用来配搭val在当中前数据当中是否存在，采用二分法
     *
     * 优点 ： 数据量越大速度速度
     *
     * 缺点 ： 构建有序数据的时候 ，会产生时间以及空间消耗
     *
     * @param val
     * @return
     */
     public int binarySearch(int val){
         //把所有元素排序并产生一个新的数组
        int[] orderArr = sortByNewArray();
        //二分
         int start = 0;
         int end = orderArr.length - 1;
         //计算 中间指针
         while(start <= end){
            int mid = (start + end) >> 1;
             if(orderArr[mid] == val){
                 //中间这个位置上的数就是你想要的
                 return mid;
             }else if(orderArr[mid] < val){
                 start = mid + 1;
             }else{
                 end = mid - 1;
             }
         }
         return -1;
     }

    /**
     * 是否可以把我们的数据 弄成有序   升 降
     * 冒泡
     */
    /**
     * 有来对现在元素 进行排序操作
     * 设计 :  开发一个自定义类型的时候 要遵循的规范是什么
     * 1 : 单一职责 : 方法功能单一 .... 就是一个方法最好只有一个功能
     * --> 高内聚低耦合  代码重用性问题 重构
     *
     * @return
     */
    public int[] sortByNewArray() {
        //1 数组有效元素 移动
        int[] temp = effectArray();
        //2 排序
        return sortByAsc(temp);
    }

    /**
     * 对指定数组进行升度排列
     *
     * @param array 指定数组
     * @return
     */
    public int[] sortByAsc(int[] array) {
        for (int i = 0, len = array.length - 1; i < len; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                //升序  降序
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
        return array;
    }

    /**
     * 对数组里面的两个指定下标进行交换操作
     *
     * @param array 数组
     * @param start 开始下标
     * @param end   结束下标
     */
    public void swap(int[] array, int start, int end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }

    /**
     * 返回changeArray里面全部的有效元素，并生成新的数组
     *
     * @return int[]
     */
    public int[] effectArray() {
//        int[] newArray = new int[size()];
//        for (int i = 0, len = size(); i < len; i++) {
//            newArray[i] = arr[i];
//        }
//        return newArray;
        return Arrays.copyOf(arr,index);
    }

    /**
     * 删除现有元素
     * 1 ： 最后一个元素  .index --,下次一次add时，覆盖了
     * 2 : 中间元素 ，向前移动:
     * @param subscript  指定的下标
     */
    public boolean del(int subscript){
        if(index <= subscript){
            return false;
        }

        for(int i = subscript + 1;i < index;i++){
            arr[i - 1] = arr[i];
        }
        index --;
        return true;
    }

    /**
     * 获得当前数组里面现有元素（通过add添加进来几个）个数
     * <p>
     * 说白了就是有几个元素 ，现在有元素个数
     *
     * @return int
     */
    public int size() {
        return index;
    }


    public static void main(String[] args) {
        ChangeArray ca = new ChangeArray();
        ca.add(1);
        ca.add(2);
        ca.add(3);
        ca.add(5);
        ca.add(7);
        ca.add(4);
        //二分查找 : 返回的是排序以后的下标
        System.out.println(ca.binarySearch(4));


        //删除功能
        System.out.println(Arrays.toString(ca.effectArray()));

        System.out.println("删除掉我们的最后一位");
        ca.del(0);
        ca.add(6);

        System.out.println(Arrays.toString(ca.effectArray()));

        //二分   删除 []  数组帮助类

//        我们经过我们自己的努力，完成一些代码，通过我们的代码实现了一些功能
        //基本  自己写的引用类型

        //数组 ： 连续，

        //可以把我们自己写的这个类，起一个名字呀

        //动态数组操作

        //物理存储结构 ： 顺序 [数组 有连续下标，开辟是不是连续] 链式

        //逻辑存储结构 ： 线性表 [满足一些规范]

        //我们自己编写一套

        //老外也有一套  Arrays


    }

}
